#include "abb.h"
#include "pila.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

/* ******************************************************************
 *                DEFINICION DE LOS TIPOS DE DATOS                  *
 * *****************************************************************/

typedef struct abb_nodo {
	void* dato;
	char* clave;
	struct abb_nodo* izq;
	struct abb_nodo* dcho;
} abb_nodo_t;
	
struct abb {
	abb_nodo_t* raiz;
	size_t cantidad;
	abb_comparar_clave_t comparar_f;
	abb_destruir_dato_t destruir_dato_f;
};

struct abb_iter {
	pila_t* pila;
};

/* ******************************************************************
 *            			PRIMITIVAS AUXILIARES						*
 * *****************************************************************/
					  /* FUNCIONES INTERNAS */
			  /* IMPLEMENTACION AL FINAL DEL ARCHIVO */

// Crea un nodo para el ABB con los parametros pasados.
// Devuelve NULL en caso de error.
// Post: se devolvió el nodo con la información correspondiente.
abb_nodo_t* abb_crear_nodo (const char* clave, void* valor);

// Destruye el nodo pasado por parámetro. En caso de recibir una
// función por el 2do parámetro, ésta es llamada para aplicársela al
// dato del nodo.
// Pre: el nodo fue creado.
// Post: el nodo y su dato fueron destruidos.
void abb_destruir_nodo (abb_nodo_t *nodo, abb_destruir_dato_t f);

// función auxiliar de 'abb_guardar'. Crea el nodo, almacena la info
// y aumenta la cantidad. Devuelve falso en caso de error.
// Pre: 'nodo' debe ser NULL, el resto debe ser válido.
// Post: se creó el nodo, se le agregó la info y se aumentó la cantidad.
bool abb_guardar_en_nodo (abb_nodo_t **nodo, const char *clave, void *dato, size_t *cantidad);

// función auxiliar de 'abb_guardar'. Agrega un nuevo elemento al ABB
// y manipula su cantidad. Trabaja con nodos, devuelve falso en caso de error.
// Pre: 'clave', 'cmp' y 'cantidad' deben ser válidos, el resto puede ser NULL.
// Post: se agregó el nuevo elemento o dato al ABB.
bool abb_guardar_2 (abb_nodo_t **nodo, const char *clave, void *dato, abb_comparar_clave_t cmp, abb_destruir_dato_t dtr, size_t *cantidad);

// Función auxiliar de 'abb_obtener'. Obtiene el valor correspondiente
// a la clave pasada al ABB. Recibe un nodo, no un ABB.
// Devuelve NULL en caso de no existir.
// Pre: todos los parámetros fueron creados y son válidos.
// Post: en caso de existir, se devolvió el valor solicitado
// sin removerlo del ABB.
void* abb_obtener_2 (const abb_nodo_t *nodo, const char* clave, abb_comparar_clave_t cmp);

// Saca el elemento correspondiente a la clave pasada y actualiza la cantidad.
// Devuelve NULL en caso de no existir. Trabaja con nodos.
// Pre: todos los parámetros son válidos.
// Post: en caso de existir, se devolvió el valor solicitado habiéndolo
// removido del ABB previamente. El ABB contiene un elemento menos y fue 
// reordenado.
void* abb_borrar_2 (abb_nodo_t **nodo, const char *clave, abb_comparar_clave_t cmp, size_t *cantidad);

// Función auxiliar de 'abb_borrar'. Saca el dato del nodo pasado por parámetro,
// reacomoda el ABB y actualiza su cantidad.
// Pre: el nodo fue creado.
// Post: se devolvió dicho valor. El ABB contiene un elemento menos
// y fue reordenado.
void* abb_borrar_en_nodo (abb_nodo_t **nodo, size_t *cantidad);

// Itera internamente por los nodos 'in order', es decir, izq-raíz-der.
// Si se recibe 'funcion', ésta será aplicada a cada uno de ellos.
// El puntero a void 'extra' será pasado como último parámetro de 'funcion'.
// Pre: el nodo fue creado.
// Post: se iteró por todos los nodos 'in order' aplicando 'funcion' a cada elemento.
void abb_in_order_2 (abb_nodo_t **nodo, bool funcion(const char *, void *, void *), void *extra);

// Apila todos los nodos izquierdos que tenga el tope actual.
// Devuelve falso en caso de que la pila esté vacía o de error.
// Pre: el iter fue creado.
// Post: de existir, se apilaron los nodos izquierdos.
bool abb_iter_apilar_izq (abb_iter_t *it);

/* ******************************************************************
 *              IMPLEMENTACION DE PRIMITIVAS DEL ABB				*
 * *****************************************************************/
	
// Crea un ABB. Si se recibe la función destruir_dato por parámetro,
// para cada uno de los elementos del ABB, llama a destruir_dato.
// Si se recibe comparar_clave (cmp), se la utiliza para los elementos dos a dos.
// Pre: destruir_dato es una función capaz de destruir los datos del árbol
// y cmp de comparar dos claves, o NULL en caso de no utilizarlas.
// Post: devuelve un nuevo ABB vacío.
abb_t* abb_crear (abb_comparar_clave_t cmp, abb_destruir_dato_t destruir_dato) {
	abb_t* arbol = (abb_t*) calloc (1,sizeof(abb_t));
	if (!arbol) return NULL;

	arbol->cantidad = 0;
	arbol->comparar_f = cmp;
	arbol->destruir_dato_f = destruir_dato;
	return arbol;
}

// Destruye el ABB.
// Pre: el ABB fue creado.
// Post: se eliminaron todos los elementos del ABB.
void abb_destruir (abb_t *arbol) {
	if (!arbol) return;
	abb_destruir_nodo(arbol->raiz,arbol->destruir_dato_f);
	free(arbol);
}

// Devuelve la cantidad de elementos existentes en el ABB.
// Pre: el ABB fue creado.
// Post: se devolvió la cantidad de elementos del ABB.
// En caso de estar vacío, lógicamente, la función devuelve 0 (cero).
size_t abb_cantidad (abb_t *arbol) {
	if (!arbol) return 0;
	return (arbol->cantidad);
}

// Agrega un nuevo elemento al ABB. Devuelve falso en caso de error.
// Pre: el ABB fue creado.
// Post: se agregó un nuevo elemento al ABB.
bool abb_guardar (abb_t *arbol, const char *clave, void *dato) {
	if (!arbol) return false;
	return abb_guardar_2 (&(arbol->raiz),clave,dato,arbol->comparar_f,arbol->destruir_dato_f,&(arbol->cantidad));
}

// Obtiene el valor correspondiente a la clave pasada al ABB.
// Devuelve NULL en caso de no existir.
// Pre: el ABB fue creado.
// Post: en caso de existir, se devolvió el valor solicitado
// sin removerlo del ABB.
void* abb_obtener (const abb_t *arbol, const char* clave) {
	if (!arbol) return NULL;
	if (!(arbol->raiz)) return NULL;
	return abb_obtener_2 (arbol->raiz,clave,arbol->comparar_f);
}

// Devuelve verdadero si la clave contiene algún valor adjunto,
// falso en caso contrario.
// Pre: el ABB fue creado.
// Post: se informó el 'estado' de la clave.
bool abb_pertenece (const abb_t *arbol, const char *clave) {
	void* valor = abb_obtener(arbol,clave);
	if (!valor) return false;
	return true;
}

// Saca el elemento correspondiente a la clave pasada.
// Devuelve NULL en caso de no existir.
// Pre: el ABB y la clave son parámetros válidos.
// Post: en caso de existir, se devolvió el valor solicitado habiéndolo
// removido del ABB previamente. El ABB contiene un elemento menos y fue 
// reordenado.
void* abb_borrar (abb_t *arbol, const char *clave) {
	if ((!arbol) || (!clave)) return NULL;
	return abb_borrar_2(&(arbol->raiz), clave,arbol->comparar_f, &(arbol->cantidad));
}

// Itera internamente por el ABB 'in order', es decir, izq-raíz-der.
// Si se recibe 'funcion', ésta será aplicada a cada elemento.
// El puntero a void 'extra' será pasado como último parámetro de 'funcion'.
// Pre: el ABB fue creado.
// Post: se iteró por todo el ABB 'in order' aplicando 'funcion' a cada elemento.
void abb_in_order (abb_t *arbol, bool funcion(const char *, void *, void *), void *extra) {
	if (!arbol) return;
	if (!(arbol->raiz)) return;
	
	abb_in_order_2(&(arbol->raiz),funcion,extra);
}

/* *****************************************************************
 *               IMPLEMENTACION PRIMITIVAS DEL ITERADOR            *
 * *****************************************************************/

// Crea un iterador.
// Pre: el ABB fue creado.
// Post: se creó un iterador que apunta hacia la primer raíz del ABB.
abb_iter_t* abb_iter_in_crear (const abb_t *arbol) {
	abb_iter_t* it = (abb_iter_t*) malloc(sizeof(abb_iter_t));
	if (!it) return NULL;
	
	it->pila = pila_crear();
	if (!(it->pila)) { free (it); return NULL; }
	if (arbol->raiz) {
		bool apilo_raiz = pila_apilar(it->pila,arbol->raiz);
		bool apilo_izq = abb_iter_apilar_izq(it);
		if ((!apilo_raiz) || (!apilo_izq)) {
			pila_destruir(it->pila,NULL);
			free (it);
			return NULL;
		}
	}
	return it;
}

// El iterador avanza a la siguiente raíz u hoja. Si el ABB
// no tiene elementos o el iterador se encuentra al final de él, devuelve falso.
// Pre: el ABB y el iterador fueron creados.
// Post: el iterador avanzó a la siguiente posición (de ser posible).
bool abb_iter_in_avanzar (abb_iter_t *iter) {
	abb_nodo_t* nodo = pila_ver_tope(iter->pila);
	if (!nodo) return false;
	
	nodo = pila_desapilar(iter->pila);
	if (nodo->dcho) {
		if (!pila_apilar(iter->pila,nodo->dcho)) return false;
		if (!abb_iter_apilar_izq(iter)) return false;
	}
	return true;
}

// Da la clave de la posición donde se encuentra el iterador.
// Pre: el ABB y el iterador fueron creados.
// Post: se devolvió la clave de la posición donde se encuentra el iterador.
const char* abb_iter_in_ver_actual (const abb_iter_t *iter) {
	abb_nodo_t* nodo = pila_ver_tope(iter->pila);
	if (!nodo) return NULL;
	return (nodo->clave);
}

// Devuelve verdadero si el iterador se encuentra al final del ABB,
// falso en caso contrario.
// Pre: el ABB y el iterador fueron creados.
bool abb_iter_in_al_final (const abb_iter_t *iter) {
	if (!abb_iter_in_ver_actual(iter)) return true;
	return false;
}

// Destruye el iterador.
// Pre: el iterador fue creado.
// Post: se destruyó el iterador.
void abb_iter_in_destruir (abb_iter_t* iter) {
	pila_destruir(iter->pila,NULL);
	free(iter);
}

/* ******************************************************************
 *            IMPLEMENTACION DE PRIMITIVAS AUXILIARES				*
 * *****************************************************************/

// Crea un nodo para el ABB con los parametros pasados.
// Devuelve NULL en caso de error.
// Post: se devolvió el nodo con la información correspondiente.
abb_nodo_t* abb_crear_nodo (const char* clave, void* valor) {
	abb_nodo_t* nodo = (abb_nodo_t*) calloc(1,sizeof(abb_nodo_t));
	if (!nodo) return NULL;
	
	size_t largo = 0;
	while (clave[largo] != '\0') largo++;
	nodo->clave = (char*) malloc( (largo+1) * sizeof(char) );
	if (!(nodo->clave)) return NULL;
	
	strcpy (nodo->clave , clave);
	nodo->clave[largo] = '\0';
	nodo->dato = valor;
	return nodo;
}

// Destruye el nodo pasado por parámetro. En caso de recibir una
// función por el 2do parámetro, ésta es llamada para aplicársela al
// dato del nodo.
// Pre: el nodo fue creado.
// Post: el nodo y su dato fueron destruidos.
void abb_destruir_nodo (abb_nodo_t* nodo, abb_destruir_dato_t f) {
	if (!nodo) return;
	if (nodo->izq) abb_destruir_nodo(nodo->izq,f);
	if (nodo->dcho) abb_destruir_nodo(nodo->dcho,f);
	if (nodo->clave) free (nodo->clave);
	if (f) f(nodo->dato);
	free (nodo);
}

// función auxiliar de 'abb_guardar'. Crea el nodo, almacena la info
// y aumenta la cantidad. Devuelve falso en caso de error.
// Pre: 'nodo' debe ser NULL, el resto debe ser válido.
// Post: se creó el nodo, se le agregó la info y se aumentó la cantidad.
bool abb_guardar_en_nodo (abb_nodo_t **nodo, const char *clave, void *dato, size_t *cantidad) {
	if (*nodo) return false;
	*nodo = abb_crear_nodo (clave, dato);
	if (!(*nodo)) return false;
	(*cantidad)++;
	return true;
}

// función auxiliar de 'abb_guardar'. Agrega un nuevo elemento al ABB
// y manipula su cantidad. Trabaja con nodos, devuelve falso en caso de error.
// Pre: 'clave', 'cmp' y 'cantidad' deben ser válidos, el resto puede ser NULL.
// Post: se agregó el nuevo elemento o dato al ABB.
bool abb_guardar_2 (abb_nodo_t **nodo, const char *clave, void *dato, abb_comparar_clave_t cmp, abb_destruir_dato_t dtr, size_t *cantidad) {
	if (!(*nodo)) return abb_guardar_en_nodo (nodo,clave,dato,cantidad);
	if (!((*nodo)->clave) || (!clave) || (!cmp)) return false;
	
	int rdo = cmp(clave,(*nodo)->clave);
	if (rdo > 0) return abb_guardar_2 (&((*nodo)->dcho),clave,dato,cmp,dtr,cantidad);
	if (rdo < 0) return abb_guardar_2 (&((*nodo)->izq), clave,dato,cmp,dtr,cantidad);
	if (rdo == 0) {
		if ((dtr)&&((*nodo)->dato)) dtr((*nodo)->dato);
		(*nodo)->dato = dato;
	}
	return true;
}

// Función auxiliar de 'abb_obtener'. Obtiene el valor correspondiente
// a la clave pasada al ABB. Recibe un nodo, no un ABB.
// Devuelve NULL en caso de no existir.
// Pre: todos los parámetros fueron creados y son válidos.
// Post: en caso de existir, se devolvió el valor solicitado
// sin removerlo del ABB.
void* abb_obtener_2 (const abb_nodo_t *nodo, const char* clave, abb_comparar_clave_t cmp) {
	if (!nodo) return NULL;
	if ((!(nodo->clave)) || (!clave)) return NULL;
	if (cmp) {
		int rdo = cmp(clave,nodo->clave);
		if (rdo > 0)  return abb_obtener_2(nodo->dcho,clave,cmp);
		if (rdo == 0) return nodo->dato;
		if (rdo < 0)  return abb_obtener_2(nodo->izq,clave,cmp);
	}
	return NULL;
}

// Saca el elemento correspondiente a la clave pasada y actualiza la cantidad.
// Devuelve NULL en caso de no existir. Trabaja con nodos.
// Pre: todos los parámetros son válidos.
// Post: en caso de existir, se devolvió el valor solicitado habiéndolo
// removido del ABB previamente. El ABB contiene un elemento menos y fue 
// reordenado.
void* abb_borrar_2 (abb_nodo_t **nodo, const char *clave, abb_comparar_clave_t cmp, size_t *cantidad) {
	if (!(*nodo)) return NULL;
	if (!((*nodo)->clave)) return NULL;
	if (cmp) {
		int rdo = cmp(clave,(*nodo)->clave);
		if (rdo > 0)  return abb_borrar_2(&((*nodo)->dcho),clave,cmp,cantidad);
		if (rdo == 0) return abb_borrar_en_nodo(nodo,cantidad);
		if (rdo < 0)  return abb_borrar_2(&((*nodo)->izq),clave,cmp,cantidad);
	}
	return NULL;
}

/*----------------NECESARIAS PARA 'abb_borrar_en_nodo'----------------*/
// función auxiliar del 'abb_borrar_en_nodo'. Reemplaza 'nodo' por 'actual'
// salvando la información que haga falta según el caso.
// Pre: todos los parámetros son válidos.
// Post: se reemplazó la raíz de 'arbol' por la de 'actual'.
bool abb_reemplazar_nodo (abb_nodo_t **nodo, abb_nodo_t **actual, char* modo) {
	if ((!(*nodo)) || (!(*actual)) || (!modo)) return false;
	if (strcmp(modo,"derecha") == 0) {
		(*actual)->izq = (*nodo)->izq;
	}else{ (*actual)->dcho = (*nodo)->dcho; }
	
	abb_nodo_t *aux = *nodo;
	(*nodo) = (*actual);
	free(aux);
	
	return true;
}

// función auxiliar del 'abb_borrar_en_nodo'.
// Itera a lo largo del ABB hasta encontrar una hoja y devuelve su padre.
// Pre: todos los parámetros son válidos.
// Post: se encontró una hoja, se la almacenó en 'actual'.
abb_nodo_t* abb_buscar_hoja (abb_nodo_t **nodo, abb_nodo_t *actual, abb_nodo_t *siguiente, char* modo) {
	abb_nodo_t *anterior = *nodo;
	while (siguiente) {
		anterior = actual;
		actual = siguiente;
		if (strcmp(modo,"derecha") == 0) {
			siguiente = actual->izq;
		}else{ siguiente = actual->dcho; }
	}
	return anterior;
}

// función auxiliar del 'abb_borrar_en_nodo'.
// Actualiza 'nodo' con 'actual'.
// Pre: todos los parámetros son válidos.
// Post: se actualizó 'nodo' a partir de 'actual'.
void abb_actualizar_raices (abb_nodo_t **nodo, abb_nodo_t *anterior, char* modo) {
	abb_nodo_t *aux;
	if (strcmp(modo,"derecha") == 0) {
		aux = anterior->izq;
		anterior->izq = anterior->izq->dcho;
	}else{
		aux = anterior->dcho;
		anterior->dcho = anterior->dcho->izq;
	}
	
	(*nodo)->clave = aux->clave;
	(*nodo)->dato = aux->dato;
	free(aux);
}

// función auxiliar del 'abb_borrar_en_nodo'. Reordena el ABB trabajando con nodos.
// Pre: todos los parámetros son válidos.
// Post: se reordenó el ABB.
bool abb_reordenar (abb_nodo_t **nodo, abb_nodo_t **actual, char* modo) {
	if (!(*actual)) return false;
	abb_nodo_t* siguiente;
	
	if (strcmp(modo,"derecha") == 0) {
		siguiente = (*actual)->izq;
	}else{ siguiente = (*actual)->dcho; }
	
	if (!siguiente) return abb_reemplazar_nodo(nodo,actual,modo);
	
	abb_nodo_t *anterior = abb_buscar_hoja (nodo,*actual,siguiente,modo);
	abb_actualizar_raices (nodo,anterior,modo);
	
	return true;
}
/*--------------------------------------------------------------------*/
// Función auxiliar de 'abb_borrar'. Saca el dato del nodo pasado por parámetro,
// reacomoda el ABB y actualiza su cantidad.
// Pre: el nodo fue creado.
// Post: se devolvió dicho valor. El ABB contiene un elemento menos
// y fue reordenado.
void* abb_borrar_en_nodo (abb_nodo_t **nodo, size_t *cantidad) {
	free((*nodo)->clave);
	void* valor = (*nodo)->dato;
	(*nodo)->dato = NULL;
	(*cantidad)--;

	abb_nodo_t **actual = &((*nodo)->dcho);
	if (abb_reordenar(nodo,actual,"derecha")) return valor;

	actual = &((*nodo)->izq);
	if (abb_reordenar(nodo,actual,"izquierda")) return valor;
	
	free((*nodo));
	(*nodo) = NULL;
	return valor;
}

// Itera internamente por los nodos 'in order', es decir, izq-raíz-der.
// Si se recibe 'funcion', ésta será aplicada a cada uno de ellos.
// El puntero a void 'extra' será pasado como último parámetro de 'funcion'.
// Pre: el nodo fue creado.
// Post: se iteró por todos los nodos 'in order' aplicando 'funcion' a cada elemento.
void abb_in_order_2 (abb_nodo_t **nodo, bool funcion(const char *, void *, void *), void *extra) {
	if (!(*nodo)) return;
	if (!((*nodo)->clave)) return;
	
	if ((*nodo)->izq) abb_in_order_2 (&((*nodo)->izq),funcion,extra);
	if (funcion) funcion((*nodo)->clave,(*nodo)->dato,extra);
	if ((*nodo)->dcho) abb_in_order_2 (&((*nodo)->dcho),funcion,extra);
}

// Apila todos los nodos izquierdos que tenga el tope actual.
// Devuelve falso en caso de que la pila esté vacía o de error.
// Pre: el iter fue creado.
// Post: de existir, se apilaron los nodos izquierdos.
bool abb_iter_apilar_izq (abb_iter_t* it) {
	abb_nodo_t* tope = pila_ver_tope(it->pila);
	if (!tope) return false;
	if (!(tope->izq)) return true;
	
	if (!pila_apilar(it->pila,tope->izq)) return false;
	return abb_iter_apilar_izq(it);
}
